#include <iostream>
#include <fstream>
#include "huffmanTree.h"

//压缩文件结构：
//每4个字节表示一个unsigned long类型
//开头用4个字节存储源文件长度
//然后连续用256x4个字节依次存储256个数据的权值(0x00~0xff)
//之后存储编码后的压缩数据
//压缩信息数据大小=257x4=1028 Bytes
//【】【】【】【】
//【】【】【】【】x256
//【】【】。。。。。。。



huffmanNode::huffmanNode()
{
    data = 0;
    isChosen = 0;
    isLeaf = 0;
    weight = 0;
    left = right = next = NULL;
}


codeChart::codeChart()
{
    code = new char[256];
    for(int t = 0; t < 256; t ++)
        code[t] = '0';
    codeLen = 0;
}

codeChart::~codeChart()
{
    delete [] code;
}


huffmanTree::huffmanTree()
{
    writeBuf = new char[512];
    begin = end = 0;
    fileLen = 0;

}


huffmanTree::~huffmanTree()
{
    delete [] writeBuf;
    huffmanNode* tmpNode = tree.next;
    huffmanNode* deleteNode;
    while(tmpNode != NULL)
    {
        deleteNode = tmpNode;
        tmpNode = tmpNode->next;
        delete deleteNode;
    }

}

int huffmanTree::buildHuffmanTree(char *filePath)
{
    weightStatis(filePath);
    buildTreeFromWeight();
    return 1;

}


int huffmanTree::weightStatis(char *filePath)
{
    huffmanNode* tmpNode;

    //创建叶子节点，8位256个
    for(int t = 0; t < 256; t ++)
    {
        tmpNode = new huffmanNode;
        tmpNode->data = t;
        tmpNode->isLeaf = 1;
        tmpNode->next = tree.next;
        tree.next = tmpNode;
    }

    leafNode = tree.next;


    //printWeight();


    std::fstream oriFile;
    oriFile.open(filePath, std::ios::binary | std::ios::in);



    //统计各叶子节点的权值
    char buf;

    oriFile.read(&buf, sizeof(char));

    while(oriFile.eof() == 0)
    {
        fileLen ++;
        freshWeight(buf);
        oriFile.read(&buf, sizeof(char));
    }

    oriFile.close();


    return 1;

}


int huffmanTree::buildTreeFromWeight()
{
    huffmanNode *tmpNode;
    unsigned long small, smaller;     //次小值，最小值
    huffmanNode *smallNode, * smallerNode;  //次小值节点，最小值节点
    int initState;      //辅助变量
    int endSign = 0;    //循环结束标记

    while(endSign == 0)
    {
        endSign = 1;

        //寻找最小值
        initState = 0;
        tmpNode = tree.next;
        while(tmpNode != NULL)
        {
            if(tmpNode->isChosen == 0)
            {
                if(initState == 0)
                {
                    smaller = tmpNode->weight;
                    smallerNode = tmpNode;
                    initState = 1;
                }
                else
                {
                    if(tmpNode->weight < smaller)
                    {
                        smaller = tmpNode->weight;
                        smallerNode = tmpNode;
                    }
                }
            }
            tmpNode = tmpNode->next;
        }

        //寻找次小值
        initState = 0;
        tmpNode = tree.next;
        while(tmpNode != NULL)
        {
            if(tmpNode->isChosen == 0 && tmpNode != smallerNode)
            {
                endSign = 0;        //若无次小值，则哈夫曼树已构建
                if(initState == 0)
                {
                    small = tmpNode->weight;
                    smallNode = tmpNode;
                    initState = 1;
                }
                else
                {
                    if(tmpNode->weight < small)
                    {
                        small = tmpNode->weight;
                        smallNode = tmpNode;
                    }
                }
            }
            tmpNode = tmpNode->next;
        }



        //std::cout << "here" << std::endl;

        if(endSign == 1)
        {
            tree.next = smallerNode;
            break;
        }

        //将最小值和次小值合并成一个节点
        smallerNode->isChosen = 1;
        smallNode->isChosen = 1;
        tmpNode = new huffmanNode;
        //tmpNode = tree.next;

        tmpNode->next = tree.next;
        tree.next = tmpNode;
        tmpNode->weight = smallNode->weight + smallerNode->weight;
        tmpNode->left = smallNode;
        tmpNode->right = smallerNode;

    }//while

    return 1;
}


int huffmanTree::compress(char *oriFilePath, char *outPutFile)
{
    bufOutPut.open(outPutFile, std::ios::binary | std::ios::out);
    std::fstream bufOriFile;
    bufOriFile.open(oriFilePath, std::ios::binary | std::ios::in);


    writeFileData();        //写压缩文件数据

    char in;
    bufOriFile.read(&in, sizeof(char));

    //将指定数据对应的哈夫曼编码写到压缩文件中去
    while(bufOriFile.eof() == 0)
    {
        writeBufToFile(in);
        bufOriFile.read(&in, sizeof(char));
    }

    writeBufToFile(in, 1);
    bufOriFile.close();
    bufOutPut.close();

    return 1;

}

int huffmanTree::huffmanCompress(char *oriFile, char *outPutFile)
{
    //weightStatis(oriFile);
    buildHuffmanTree(oriFile);      //构建哈夫曼数
    getCodeChart();                 //获取编码表
    //writeCodeData();
    compress(oriFile, outPutFile);  //压缩文件
    return 1;


}

int huffmanTree::huffmanDecompress(char *compressedFile, char *outPutFile)
{
    decompress(compressedFile, outPutFile);
    return 1;

}



int huffmanTree::freshWeight(char buf)
{
    huffmanNode *tmpNode = tree.next;

    while(tmpNode != NULL)
    {
        if(tmpNode->data == buf)
        {
            //std::cout << "here" << std::endl;
            tmpNode->weight ++;
            return 1;
        }
        tmpNode = tmpNode->next;
    }
    return 1;
}



int huffmanTree::printWeight()
{
    huffmanNode* tmpNode = tree.next;
    int weight = 0;
    while(tmpNode != NULL)
    {
        std::cout << std::hex << (short int) tmpNode->data << " : " << std::dec << tmpNode->weight << std::endl;
        weight += tmpNode->weight;
        tmpNode = tmpNode->next;
    }

    std::cout << weight << std::endl;
    return 1;
}


int huffmanTree::getCodeChart()
{
    char codeStack[256];
    int current = 0;

    codeStack[current] = '0';
    getCodeChartRe(codeStack, current, tree.next->left);

    codeStack[current] = '1';
    getCodeChartRe(codeStack, current, tree.next->right);
    return 1;
}


int huffmanTree::getCodeChartRe(char *s, int c, huffmanNode *n)
{
    //int a;
    if(n->isLeaf == 1)      //到达叶子节点
    {
        for(int t = 0; t <= c; t ++)
        {
            //a = s[t];
            //a = (hfmCodeChart[(int)(n->data)].code)[t];
            //a = s[t];
            //a = (unsigned char)(n->data);
            (hfmCodeChart[(unsigned char)(n->data)].code)[t] = s[t];    //存储编码到编码表中
        }
        hfmCodeChart[(unsigned char)(n->data)].codeLen = c;             //存储编码长度
        return 1;
    }

    s[c+1] = '0';
    getCodeChartRe(s, c+1, n->left);

    s[c+1] = '1';
    getCodeChartRe(s, c+1, n->right);

    return 1;

}


int huffmanTree::printCodeChart()
{
    for(int t = 0; t < 256; t ++)
    {
        std::cout << t << " : ";
        for(int t2 = 0; t2 <= hfmCodeChart[t].codeLen; t2 ++)
        {
            std::cout << (hfmCodeChart[t].code)[t2];
        }
        std::cout << std::endl;
    }
    return 1;
}


int huffmanTree::writeBufToFile(char data, int isFinish)
{
    if(isFinish == 1)       //将剩余数据写到文件中去
    {
        char r = 0;
        char tf = 0;
        int count = 7;
        int isWriteLastByte = 0;
        while(begin != end)
        {
            isWriteLastByte = 1;
            r |= ((tf|(writeBuf[begin]-'0')) << count);
            begin = (begin+1)%512;
            count --;
        }
        if(isWriteLastByte == 1)
        {
            bufOutPut.write(&r, sizeof(char));
        }

        return 1;
    }

    //将新数据加入到缓冲区中
    for(int t = 0; t <= hfmCodeChart[(unsigned char) data].codeLen; t ++)
    {
        writeBuf[end] = hfmCodeChart[(unsigned char) data].code[t];
        end = (end+1) % 512;
    }

    char result = 0;
    char tmp = 0;
    //将缓冲区的数据每8位储存到文件中
    while( (end >= begin && end - begin >= 8)
           || (end < begin && end + (512 - begin) >= 8))    //条件为数据量大于8位
    {
        result = 0;

        for(int t = begin; t < begin + 8; t ++)
        {
            result |= ((tmp | (writeBuf[t%512]-'0')) << (7-(t-begin)));
        }
        bufOutPut.write(&result, sizeof(char));

        begin = (begin+8) % 512;
    }

    return 1;

}


int huffmanTree::decompress(char *compressedFile, char *outPutFile)
{
    bufReadFile.open(compressedFile, std::ios::binary | std::ios::in);
    bufOutPut.open(outPutFile, std::ios::binary | std::ios::out);

    readFileData();             //从文件中读取压缩数据，权值
    buildTreeFromWeight();      //重建哈夫曼数

    begin = end = 0;
    huffmanNode* tmpNode = tree.next;
    char readFile;          //读入的数据
    uint32_t tmpFileLen = 0;   //文件长度

    int isFinish = 0;       //结束标记
    //bufReadFile.read(&readFile, sizeof(char));

    while(isFinish == 0)
    {
        //读入新数据到缓冲区
        if(begin == end)
        {
            bufReadFile.read(&readFile, sizeof(char));
            if(bufReadFile.eof() == 1)      //到文件结尾
            {
                //std::cout << "111";
                break;
            }
            for(int t = end; t < end + 8; t ++)
            {
                writeBuf[t%512] = ((readFile >> (7 - (t - end))) & 1) + '0';
            }
            end = (end+8) % 512;
        }

        //根据读入的数据遍历哈夫曼树
        while(true)
        {
            if(tmpNode->isLeaf == 1)        //到达叶子节点，将节点的数据写入到文件中
            {
                bufOutPut.write(&(tmpNode->data), sizeof(char));
                tmpFileLen ++;
                //std::cout << fileLen << tmpFileLen <<std::endl;
                if(tmpFileLen >= fileLen)
                {
                    isFinish = 1;
                    //std::cout << "222";
                    break;
                }
                tmpNode = tree.next;        //重置节点为哈夫曼树的顶点
                //continue;
            }

            if(begin == end)                //缓冲区数据已读完
            {
                break;
            }

            //遍历哈夫曼树
            if(writeBuf[begin] == '0')
            {
                tmpNode = tmpNode->left;
            }
            else
            {
                tmpNode = tmpNode->right;
            }
            begin = (begin+1) % 512;

        }

    }

    bufOutPut.close();
    bufReadFile.close();
    return 1;
}


int huffmanTree::writeFileData()
{
    char tmpC;
    //写4个字节文件长度
    for(int t = 0; t < 4; t ++)
    {
        tmpC = *(((char*)&fileLen)+t);
        bufOutPut.write(&tmpC, sizeof(char));
    }

    huffmanNode* tmpNode = leafNode;
    while(tmpNode != NULL)
    {
        //节点数据
        bufOutPut.write(&(tmpNode->data), sizeof(char));
        for(int t = 0; t < 4; t ++)     //节点权值
        {
            tmpC = *(((char*)&(tmpNode->weight))+t);
            bufOutPut.write(&tmpC, sizeof(char));
        }
        tmpNode = tmpNode->next;

    }

    return 1;
}

int huffmanTree::readFileData()
{
    char tmpC[4];
    //uint32_t tmpI;

    for(int t = 0; t < 4; t ++)
    {
        bufReadFile.read(tmpC+t, sizeof(char));
    }
    fileLen = *((uint32_t*)tmpC);       //读文件长度

    huffmanNode* tmpNode;
    //tree.next = new huffmanNode;
    //tmpNode = tree.next;
    uint32_t weight;
    for(int t = 0; t < 256; t ++)
    {
        if(t == 0)
        {
            tree.next = new huffmanNode;
            tmpNode = tree.next;
        }
        else
        {
            tmpNode->next = new huffmanNode;
            tmpNode = tmpNode->next;
        }

        tmpNode->isLeaf = 1;

        bufReadFile.read(tmpC, sizeof(char));   //读节点数据
        tmpNode->data = tmpC[0];

        for(int t2 = 0; t2 < 4; t2 ++)
        {
            bufReadFile.read(tmpC+t2, sizeof(char));
        }
        weight = *((uint32_t*)tmpC);            //读节点权值
        tmpNode->weight = weight;
    }
    leafNode = tree.next;

    return 1;
}

